package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import common.printLevelOrder3

/**
 * 2196. 根据描述创建二叉树
 * https://leetcode.cn/problems/create-binary-tree-from-descriptions/description
 *
 * ```
 * 2196. 根据描述创建二叉树
 * 给你一个二维整数数组 descriptions ，其中 descriptions[i] = [parenti, childi, isLefti] 表示 parenti 是 childi 在 二叉树 中的 父节点，二叉树中各节点的值 互不相同 。此外：
 * 如果 isLefti == 1 ，那么 childi 就是 parenti 的左子节点。
 * 如果 isLefti == 0 ，那么 childi 就是 parenti 的右子节点。
 * 请你根据 descriptions 的描述来构造二叉树并返回其 根节点 。
 * 测试用例会保证可以构造出 有效 的二叉树。
 *
 * 示例 1：
 * 输入：descriptions = [[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]]
 * 输出：[50,20,80,15,17,19]
 * 解释：根节点是值为 50 的节点，因为它没有父节点。
 * 结果二叉树如上图所示。
 *
 * 示例 2：
 * 输入：descriptions = [[1,2,1],[2,3,0],[3,4,1]]
 * 输出：[1,2,null,null,3,4]
 * 解释：根节点是值为 1 的节点，因为它没有父节点。
 * 结果二叉树如上图所示。
 *
 *
 * 提示：
 * 1 <= descriptions.length <= 104
 * descriptions[i].length == 3
 * 1 <= parenti, childi <= 105
 * 0 <= isLefti <= 1
 * descriptions 所描述的二叉树是一棵有效二叉树
 * ```
 */
class leetcode_2196 {
    @Test
    fun test_1() {
        val actual = createBinaryTree(
            arrayOf(
                intArrayOf(20, 15, 1),
                intArrayOf(20, 17, 0), intArrayOf(50, 20, 1), intArrayOf(50, 80, 0), intArrayOf(80, 19, 1)
            )
        )
        val expected = arrayListOf(50, 20, 80, 15, 17, 19)
        Assert.assertEquals(expected, printLevelOrder3(actual))
    }

    private fun createBinaryTree(descriptions: Array<IntArray>): TreeNode? {
        /**
        题型：二叉树，哈希法

        思路：
        遍历aray
        HashMap<Int,Boolean> 存放是否为头节点的值，然后过滤出头节点的值。
        HashMap<Int, TreeNode> 存放创建所有的节点。然后根据头节点的值，返回该map中头节点

        时间复杂度：O（N）
        空间复杂度：O（N）

         */

        // 1 确定函数参数以及返回值
        // 2 确定终止条件
        // 3 确定单层递归的处理逻辑： 非递归

        val heads = HashMap<Int,Boolean>()
        val nodes = HashMap<Int, TreeNode>()
        build(descriptions, heads,nodes)
        return findHead(heads,nodes)
    }

    /**
     * @param nodes 存储所有节点，key = value，v = node
     * @param heads 是否是头节点，key = value，v = true 表示 是头节点，false 表示子节点
     */
    fun build(descriptions: Array<IntArray>, heads:HashMap<Int,Boolean>, nodes:HashMap<Int, TreeNode>){
        for(item in descriptions){
            val v0 = item[0]
            val v1 = item[1]
            val v2 = item[2]

            // 若节点不存在，则创建节点
            val node0 = if (nodes.contains(v0)) nodes[v0] else TreeNode(v0)
            val node1 = if (nodes.contains(v1)) nodes[v1] else TreeNode(v1)

            // 设置V1是左孩子还是右孩子
            if (v2 == 1) {
                node0?.left = node1
            } else {
                node0?.right = node1
            }

            // 把创建的2个节点都放到map
            if (null != node0) {
                nodes.put(v0, node0)
            }
            // 标记是头节点
            if (null != node1) {
                nodes.put(v1, node1)
            }
            // 标记是子节点
            if(!heads.contains(v0)){
                heads[v0] = true
            }
            heads[v1] = false
        }
    }

    fun findHead(heads:HashMap<Int,Boolean>, nodes:HashMap<Int, TreeNode>): TreeNode?{
        // 过滤出头节点的值
        var n : Int = 0
        heads
            .filter{ it.value == true}
            .keys
            .forEach{
                n = it
            }
        return nodes[n]
    }
}